package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.entity.TreeNodeN;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的最大深度
 */
public class BiTree05_MaxTreeDepth {

    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(3, 9, 20, null, null, 15, 7);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList, 0);
        // 先序遍历这颗二叉树
        List<Integer> resultList = BiTreeUtil.preorderTraversal(root);
        System.out.println(resultList);
        int maxDepth = maxDepth3(root);
        System.out.println("最大深度：" + maxDepth);
    }

    /**
     * 104.二叉树的最大深度
     * 思路：前序遍历求深度、后序遍历求高度，而根节点的高度就是二叉树的最大深度，所以可以用前序遍历、后续遍历求的根节点高度来求的二叉树最大深度
     */
    // 解法1：后序遍历
    public static int maxDepth(TreeNode root) {
        // 递归出口
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    // 解法2：前序遍历
    public static int maxDepth = 0;

    public static int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getDepth(root, 1);// 根节点的深度是 1
        return maxDepth;
    }

    public static void getDepth(TreeNode root, int depth) {
        // 递归出口
        if (root == null) {
            return;
        }
        // 更新最大深度
        maxDepth = Math.max(maxDepth, depth);
        getDepth(root.left, depth + 1);
        getDepth(root.right, depth + 1);
    }

    // 解法3：迭代：广度优先遍历 BFS
    public static int maxDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return depth;
    }

    /**
     * 相关题目
     * 559.N叉树的最大深度
     */
    public static int maxDepth(TreeNodeN root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        List<TreeNodeN> children = root.children;
        for (TreeNodeN child : children) {
            depth = Math.max(depth, maxDepth(child));
        }
        return depth + 1;
    }

    public static int maxDepth2(TreeNodeN root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        Queue<TreeNodeN> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNodeN node = queue.poll();
                List<TreeNodeN> children = node.children;
                for (TreeNodeN child : children) {
                    queue.offer(child);
                }
            }
        }
        return depth;
    }
}
